Cream of the Crop 3

home *** CD-ROM | disk | FTP | other *** search

/ Cream of the Crop 3 / Cream of the Crop 3.iso / science / ack3d.zip / NOTES.TXT < prev next >

Wrap

Text File | 1994-01-09 | 32KB | 825 lines

ACK-3D ( Animation Construction Kit 3D ) ****************************************************************************** This file is included for completeness. It was originally distributed with the earlier version of the ACK engine and contains some of the technical notes used in the ray-casting technique. This file has not been edited for the new engine so some of the information may not apply. In general however, it gives a basic foundation for creation of one type of ray-casting engine. ****************************************************************************** Disclaimer The author, Lary Myers, and any other persons referred to in this documentation or in the computer programs ACK3D and MAPEDIT accept no responsibility for any loss of time, money or productivity, or damage to any person(s) or computer hardware or software, as a result of using the programs ACK3D and MAPEDIT, even if the above mentioned had knowledge or had been notified of the possibilities of such events. Distribution and Usage Considerable thought has gone into just how the source code for ACK3D would be released. Some possibilities included providing only the construction kit and selling the source to interested parties, or providing the source to be used as freeware for private use but requiring license for commercial ventures, and so forth. What I've decided is to release all the source, header files, notes, etc into the public domain as "PUBLICWARE". You may freely use the engine source and associated files for the programs ACK3D and MAPEDIT anyway you see fit. One of the goals when I started this project was to place the means into other peoples hands, more talented than I, so they could then create worlds of adventure and entertainment for the rest of us to share in. Here is the one reservation that I must insist on. The author, Lary Myers, hereby grants the right to use, modify, and sell the source code provided in the ACK3D collection of files, with the stipulation that Lary Myers accepts no responsibilty for changes desired in the code, bug fixes, or future updates. Now, with all that aside, PLEASE let me know of any comments and/or suggestions you may have regarding possible uses for the engine and any enhancements you wish to share with me and others. The entire project is still far from over and together maybe we can create a powerful engine for use in a wide variety of applications. ------------------------------------------------------------------------------ Programming notes: Author: Lary Myers Development system: 486DX 33Mhz 8 Meg RAM 210 Meg HD Boca VGA Microsoft mouse Borland C++ Version 3.1 Microsoft Macro Assembler Version 5.00A Languages used: C and Assembler Model used: Compact ------------------------------------------------------------------------------ Compiling the engine: 1. Place all of the files from the .ZIP file into one directory. Since I use Borland I opted for the following directory structure; \BORLANDC\ACK3D\SRC <- Contains all the source for the engine \BORLANDC\ACK3D\KIT <- Contains executables, images, for the kit 2. Several years ago I wrote a program called MK.EXE which was used to MAKE programs based on dependencies, etc. Even though the compilers nowadays have much better makes, I still use this old one of mine, so the .MAK files provided with the engine are based on using it with MK.EXE. You can either use them as is (if you have BorlandC) or use them to see what's needed to create a standard MAKE file. If you use MK then type in the following to begin the process; MK A <- This will build the ACK3D engine MK M <- This will build the Map Editor ------------------------------------------------------------------------------ Goals: 1. Create a 3D graphic engine which visually mimics the Wolfenstein 3D game as a starting point, then add new features and interface. 2. Use the engine to create a generic construction kit. 3. Provide the source and construction kit to the general public. Techniques: The graphic engine is based on a technique called Ray Casting, a term that has been used to describe the process where a 2D representation of a maze is rendered in 3D. The details of Ray Casting are provided below; 1. Using a two dimensional map similiar to graph paper, a maze is built consisting of borders (walls) in both the X and Y planes. These walls describe the physical boundaries of the map. Figure 1 shows an example of a simple map. X ╔════╦════╦════╦════╦════╦════╦════╦════╦════╦════╦════╦════╗ Y ║....║....║....║....║....║....║....║....║....║....║....║....║ ║....║....║....║....║....║....║....║....║....║....║....║....║ ╠════╬════╬════╬════╬════╬════╬════╬════╬════╬════╬════╬════╣ ║....║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║....║ ║....║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║....║ ╠════╬════╬════╬════╬════╬════╬════╬════╬════╬════╬════╬════╣ ║....║ ║ ║....║....║....║....║....║ ║ ║ ║....║ ║....║ ║ ║....║....║....║....║....║ ║ ║ ║....║ ╠════╬════╬════╬════╬════╬════╬════╬════╬════╬════╬════╬════╣ ║....║ ║ ║....║ ║ ║ ║....║ ║ ║ ║....║ ║....║ ║ ║....║ ║ ║ ║....║ ║ ║ ║....║ ╠════╬════╬════╬════╬════╬════╬════╬════╬════╬════╬════╬════╣ ║....║ ║ ║ ║ ║ ║ ║....║ ║ ║ ║....║ ║....║ ║ ║ ║ ║ ║ ║....║ ║ ║ ║....║ ╠════╬════╬════╬════╬════╬════╬════╬════╬════╬════╬════╬════╣ ║....║ ║ ║....║ ║ ║ ║....║....║....║....║....║ ║....║ ║ ║....║ ║ ║ ║....║....║....║....║....║ ╠════╬════╬════╬════╬════╬════╬════╬════╬════╬════╬════╬════╣ ║....║ ║ ║....║ ║ ║ ║ ║ ║ ║ ║....║ ║....║ ║ ║....║ ║ ║ ║ ║ ║ ║ ║....║ ╠════╬════╬════╬════╬════╬════╬════╬════╬════╬════╬════╬════╣ ║....║....║....║....║....║....║....║....║....║....║....║....║ ║....║....║....║....║....║....║....║....║....║....║....║....║ ╚════╩════╩════╩════╩════╩════╩════╩════╩════╩════╩════╩════╝ ╔════╗ ║....║ Indicates a square that has walls ║....║ ╚════╝ ╔════╗ ║ ║ Indicates a blank square ║ ║ ╚════╝ Figure 1 2. The map is made up of cubes, each having a fixed size. For our purposes we'll use 64x64 units for each square. This allows an object (or player) to move 64 units in either the X or Y direction before moving into another square. The total map is made up of a number of squares to form rows and a number of rows to form a two dimensional array (again, just like graph paper has some number or sqaures by some number of rows of squares). 3. A player is then defined as a location on the map having three properties, an X and Y coordinate as well as an Angle that the player is currently facing. Figure 2 shows this relationship. ╔════╦════╦════╦════╦ ║....║....║....║....║ ║....║....║....║....║ P - The current location of the player ╠════╬════╬════╬════╬ ║....║ ║ ║ ║ -> The current angle the player is facing ║....║ P->║ ║ ║ ╠════╬════╬════╬════╬ ║....║ ║ ║....║ ║....║ ║ ║....║ ╠════╬════╬════╬════╬ ║....║ ║ ║....║ ║....║ ║ ║....║ ╠════╬════╬════╬════╬ Figure 2 4. Once we know where the Player is and the current angle the player is facing, we can begin to determine what will be visible at that moment in time. To begin with, we need to decide on the field of vision that will be used. ACK3D uses a 60 degree field of vision to show the walls in a realistic setting. This means that the player will see all items 30 degrees to the left of the current viewing angle to 30 degrees to the right of the current angle. Figure 3 illustrates this. / / -30 degrees from viewing angle (VA - 30) / / P -------------> Current viewing angle (VA) \ \ \ +30 degrees from viewing angle (VA + 30) \ Figure 3 5. As you can see, if we superimpose Figure 3 onto figure 2 we begin to get a field of vision which encompasses those walls in front of the player (at the current viewing angle). This gives us Figure 4. 0 1 2 3 ╔════╦════╦════╦════╦ 0 ║....║....║.../║....║ ║....║....║./..║....║ P - The current location of the player ╠════╬════/════╬════╬ 1 ║....║ / ║ ║ ║ -> The current angle the player is facing ║....║ P--------> ║ ╠════╬══\═╬════╬════╬ 2 ║....║ \ ║....║ ║....║ ║ \ ║....║ ╠════╬════╬═══\╬════╬ 3 ║....║ ║ ║....║ ║....║ ║ ║....║ ╠════╬════╬════╬════╬ Figure 4 6. What the user (player) should see at this point is shown in Figure 5, where the double border represents the screen with the walls displayed inside. ╔═══════════════════════════════════╗ ║ / ║ ║ / ║ ║ / ║ ║┌───────────────────────────┐ ║ ║│ │ ║ ║│ │ ║ ║│ │ ║ ║│ │ ║ ║│ │ ║ ║│ │ ║ ║│ │ ║ ║│ │ ║ ║└───────────────────────────┘ ║ ║ \ ║ ║ \ ║ ║ \ ║ ╚═══════════════════════════════════╝ Figure 5 7. So, how do we get from a flat 2 dimensional map to the appearance of 3D walls? By calculating the height of the walls as a function of distance. Given the current X,Y coordinates of the player and the X,Y coordinates of the wall, we can use trigonometry to figure out the distance between the player and the wall. The real trick is to perform these calculations with the speed necessary to show realistic movement in our 3D environment. We'll get into that in a moment. Right now, lets look at the brute force method of determining how far the walls are. The first thing to remember is that we will be casting a ray for each column of the screen. Using VGA mode 13h this gives us 320 columns by 200 rows. So, 320 rays will be cast out to fill the screen with our field of view. 8. Lets begin by setting some initial values for the player. We said in section 2 that each square was 64 by 64 units in size. Looking at Figure 4 we see that the player is in square 1,1 about 3/4 the way down from the top of the square and about 1/4 the way over from the right side of the square. This puts our player X,Y at roughly 80,112. The current viewing angle will be 0 for this part of the discussion. Since we are going to use the trig functions provided in the C libraries, we can draw a coordinate system where the angle increases in a clockwise direction, giving us Figure 6; 270 │ 330 │ / │/ 180 ─────O───── 0 │\ │ \ │ 30 90 Figure 6 9. Therefore, as mentioned in section 4, we begin our cast 30 degrees to the left of the current view angle, or at 330 degrees, and continue until we are 30 degrees to the right of the view angle, which will be at +30 degrees. As you can see, we can form a right triangle from the player position to the point at angle 330. Opp Tan = --- /│ Adj Hyp / │ / │Opp Adj / Angle│ Cos = --- P────────┘ Hyp Adj Opp Sin = --- Hyp Figure 7 10. What we want to do at this point is draw an imaginary line from the player out to some point at angle 330. But how far do we draw the line? As far as needed to encounter a wall or until we leave the outside boundaries of the map. Lets say our map is 10 squares across by 8 rows down. That gives us 80 squares total. The maximum width of our map is therefore 64 units times 10 or 640 units, by 64 units times 8 rows or 512 units. The maximum distance we ever have to look is given be the equation; c2 = a2 + b2 (c squared = a squared plus b squared) or c2 = 640 squared plus 512 squared which gives 819.5999 or 820 units Equation 1 So, 820 units is how far we'll cast each ray, checking along the way for a wall or a boundary condition. We can use the well established Bresenham's line drawing algorithm to plot each point along the line to see what it strikes. We begin by determining the endpoints of the line. The equations for a point on a circle gives us the X and Y points we need; X1 = X + (cos(angle) * distance) Y1 = Y + (sin(angle) * distance) Equation 2 Using the numbers from section 8 and section 10 we get the following; X1 = 80 + (cos(330) * 820) Y1 = 112 + (sin(330) * 820) which gives; X1 = 790 Y1 = -298 Passing the coordinates 80,112,790,-298 into a line routine we begin to check for intercepts with walls. At each point along the line we calculate our map position with the following equation; MapPosn = ( Y / 64 ) * 10 + ( X / 64 ) Recalling that our map was 10 squares across and each square was 64 by 64 units in dimension. Looking back at Figure 4 we see that our first intercept will come when the line passes into square 2,0. At this very point we have struck a wall and can then determine the distance to that wall. We'll call the point Wx and Wy to distinguish them from our line endpoints. Using Equation 1 again we can determine the distance to the wall; c2 = a2 + b2 c2 = (Wx - x) squared plus (Wy - y) squared Equation 2 From the drawing scale in Figure 4, it appears a wall is encounterd at coordinates 128,128 in square 2,0, so we can use numbers in the above to get; c2 = (128 - 80) squared plus (128 - 112) squared which gives us; Distance = 50.596 units or 51 units rounded up Using this distance we can look up the height from a precalculated table to see how high the wall should appear on the screen. We continue this process for each column of the screen until we have a 320 columns of graphic walls displayed, each column showing the walls at a certain height, which gives the illusion of distance. As you may have already surmised, we don't advance our ray casting by whole degree increments, instead we move in 60/320 degrees or 0.1875 increments to give us a 60 degree field of view in 320 columns of the video screen. This method was initially used by the ACK3D engine and can be summarized with the following; a. Take the current viewing angle of the player and subtract 30 from it to get the cast angle. b. Calculate an X and Y endpoint using the players X,Y coordinates, the cast angle, and a maximum distance to cast the ray. c. Using Bresenham's line drawing algorithm, plot each point along the line and look for an intercept with a wall or the point where the line goes outside of the map boundaries. If a wall is found, return the Wx and Wy point of the wall intercept. d. Using the players X,Y coordinates, and the Wall Wx,Wy coordinates, calculate the distance to the wall using Equation 2. e. Use the distance to look up in a table to get the height of the wall to display. f. Add 0.1875 to the cast angle and go back to step b until 320 rays have been cast. Method 1 11. The above discussion was presented in order to give the reader some background into the train of thought for ray casting. While Method 1 did work and did produce a semi-reasonable display, some major problems were seen, these can be summarized as; a. Speed - Casting a line along every point for 320 rays was just plain SLOW! The screen could actually be seen updating from left to right as the rays were cast! (This was without any optimizations in the ray casting routines). b. Accuracy - Floating point was used in order to get the needed increments in angles and distance, but a problem with roundoff still occurred. Some of this was attributable to the code (This was pointed out to me by those who looked at the routines - my thanks to you all!). But, some of it was due to the method itself. c. Intercepts - There was no easy way to determine if we had hit a wall on the X or Y borders of the square. One method that could have been used was to determine if the Wx and Wy points fell on an even 64 boundary, but this was never tried. Once we found the correct intercept, there was still the problem of determining which column of the wall should be drawn. ------------------------------------------------------------------------------ Optimized Ray Casting: 1. Once it was determined that the method was viable, albiet with its problems, a more advanced or optimized method could be tried. This is how ACK3D evolved. 2. Many of the givens could be carried forward into the new version, we would still use squares on a map, each square being 64 units wide by 64 units tall. The player properties could still be used, giving us an X,Y coordinate pair and a current angle that the player is facing. The total viewing angle could remain at 60 degrees with a sweep from -30 degrees to the left to +30 degrees to the right of the current player angle. 3. The first order of business was to get rid of the floating point. By using fixed point numbers we could attain a speedup in the overall process. Fixed point numbers are beyond this discussion but essentially a fixed point number is where a given number is shifted a certain amount to the left to retain the fractional part of the number. This new value is then used in a calculation and the result is shifted back to the right to remove the fractional part. ACK3D uses two fixed point ranges to perform its calculations, the first being a 16 bit shift and the second being a 20 bit shift (which we'll get into soon). 4. The next thing was to begin using tables for most of the housekeeping calculations. Since we knew that our viewing angles were in 0.1875 degree increments we could precalculate sine and cosine tables (as well as tangent) ahead of time. Our full circle would therefore become 360 / 0.1875 or 1920 entries in the tables. Every angle from 0 to 360 was calculated, multiplied by 65536 (our 16 bit shift for fixed point) and written out to a file. Now if we needed to find the cosine of 330 degrees, we could use 330/0.1875 or 1760 to lookup in the cosine table and get the value 56759 (after rounding). The same holds true for sine and tangent tables (and some others) as well. 5. Now, how to speed up drawing an imaginary line from the player to a point off in the distance? Looking at the map it becomes apparent that each square is a fixed distance from each other. That is where the speedup can be found. Lets break the process down further in that we only want to look for walls that fall on the X side and then walls that fall on the Y side of the square. This means we have to cast two rays for every angle, but it also means we know in advance which intercept will occur. 0 1 2 3 ╓────╥────╥────B────╥ 0 ║....║....║.../║....║ ║....║....║./..║....║ P - The current location of the player ╟────╫────A────╫────╫ 1 ║....║ / ║ ║ ║ -> The current angle the player is facing ║....║ P--------> ║ ╟────╫──\─╫────╫────╫ 2 ║....║ C ║....║ ║....║ ║ \ ║....║ ║ Walls on the X side ╟────╫────╫───\╫────╫ 3 ║....║ ║ D....║ ─ Walls on the Y side ║....║ ║ ║....║ ╟────╫────╫────╫────╫ Figure 8 6. Figure 8 shows our section of the map with only the X walls given as double lines, the Y walls (which we'll ignore for now) all fall on the single lines. From this we can see that a ray looking only for X walls will intercept at points A and B at angle 330 (The scale and angles are not precise due to text mode limitations, for the sake of discussion lets assume that the angle is 330). We also see that points C and D will be struck at our rightmost angle of 30 degrees. This gives us a method to optimize the ray casting algorithm into the following; a. Subtract 30 degrees from the current player angle to get the viewing angle. b. Determine the Y intercept of the current square based on the view angle and the X coordinate (note that the X coordinate will be the right side of the current square if our view angle falls between 270 degrees and 90 degrees and it will be the left side of the current square if our view angle falls between 90 degrees and 270 degrees). This X,Y intercept of the current square will be the first point we look for a wall. By using the tangent or inverse tangent of the view angle we can calculate the Y or X offset depending on which ray we are casting. This gives us a starting point in the current square to begin looking for walls. Knowing the width of each square is 64 we determine the next Y coordinate that our ray will fall on if we increase (or decrease) the X intercept by 64. This can be pre-calculated and placed in a table. We continue stepping both the X and Y coordinates with addition until a wall is hit or we leave the boundaries of the map. By using Equation 1 again we see that a maximum of 13 (rounded) points along any given line is all we will ever need to traverse the maximum distance in the map. Thats 13 points verses 820 from the previous method! c. Once a wall is struck we use the Y coordinate to determine what column of the wall to display (Y AND 63) and the X coodinate to determine the distance (WITHOUT USING SQUARE ROOT). d. We flip the process around and perform a ray cast for walls that fall along the Y side of the square, using the X coordinate to determine the column of the wall and Y coordinate to determine the distance. e. Comparing the distance from the Xray and the distance from the yRay for whichever is closer we get the actual wall and wall column to display. f. Next, we advance our view angle by one unit in our 1920 entry circle and loop back to step b until 320 ray pairs have been cast. ------------------------------------------------------------------------------ Determining the height of the bitmap: 1. Once we have the distance to the wall we need to look up the display height of the bitmap from our table. This table was pre-calculated and is based on dividing the distance into an experimentally derived number (that means I tried a variety of values until one looked the best!). For ACK3D this turned out to be 18000. All distances from 1 to our max distance are divided into this number to get a height value to draw the bitmap. Heights which are too big or too small are set to the maximum or minimum values respectively. ------------------------------------------------------------------------------ Objects within our world: 1. Dealing with objects turned out to be a completely different problem. One that wasn't apparent from the effort put into the wall algorithm. The goal was to present an object to the user that did not show the same effects with angles as the walls, in other words, I didn't want objects to have corners when looking at them diaganally. This meant the distance to the object should not be dependent on either the X or the Y ray but should be based on a line of sight ray cast from the players current position. 2. After much experimenting and head scratching it was decided to treat objects using more traditional 3D methods. But, the speed still had to be considered! 3. Again, the brute force method would be to have all of the objects X and Y coordinates in a table. Each object is then translated to base 0,0 from the player and rotated into the field of vision. If the final X,Y location of the object fell within the 60 degree field of vision then the object would be visible and handled by the drawing routines. But what if there were many objects in this table? The time expended to check each object soon becomes a function of the number of objects that exist. No, some faster way had to be found. 4. So, by combining the ray casting with the process in section 3 above we could eliminate all objects not within the current field of vision thereby reducing the amount of calculations needed. This is the process; a. During the ray casting process described in section 6 above, also look in the object map to see if an object exist. If so, add the object to a list and set a flag saying the object has been seen. This flag prevents other near-angle rays from adding the same object to the list, only one entry is needed. b. Sort the object in the list with nearer objects being pushed down and farther objects being near the top. This way when the objects are later drawn the closer ones will hide objects that may be farther away and at the same angle. c. Continue the ray casting past the object just found. This allows us to find additional objects and finally any walls that may be in the line of sight. What gets returned to the caller of the ray casting routine is always the wall information, never any objects (since objects are stored in a global list). d. Once all the rays for the entire screen are cast we then draw the walls into the off-screen video buffer. Now its time to check for the objects. e. Using the list built during the ray casting we perform the laborious task of translating and rotating the objects coordinates relative to the players position and angle. This gives us final coordinates that we can use to determine where to place the object on the screen and what column to begin drawing the object. As we begin drawing, the distance to the object is checked against the distance to the corresponding wall. If the wall is closer, the object is not drawn in that column. We don't need to check the current object against all the other objects because they were sorted by distance when found, they'll cover up objects farther away by default. f. This process continues until all objects have been displayed in the list. Each time the routine is called to draw the screen we clear out the object seen flags and set the object count back to zero. This allows us to start fresh with finding any objects in our field of vision. ------------------------------------------------------------------------------ VGA Mode X: 1. During initial development it was decided to use the undocumented VGA mode X (From Michael Aprash's articles in DDJ) which allow off-screen drawing and page flipping. This worked reasonably well on fast machines, but slower machines still had problems. 2. The normal VGA 320x200 mode 13H has also been tried with good results, but it is necessary to draw to a memory buffer (the way objects are currently handled) and then copy the system memory buffer to the screen. While it is a fast and straight forward process to move the 64,000 bytes from memory to video, it was still not fast enough to use on slower machines. 3. Experimenting has shown that it is possible to setup a screen mode that gives 320x200 resolution but still has multiple pages, etc. This cuts back on the number of screen writes needed (320 columns by 40 rows) and has shown a definite increase in performance. 4. By way of the experimenting, the following files have been developed to try various methods. ACKASM.ASM - This is the current in-use file which sets multiple plane 320x200 mode. ACKASM.VGA - This uses normal VGA 320x200 mode 13h ACKASM.240 - This uses 320x240 mode X These files can be used in place of one another to test the engine in the various modes. ------------------------------------------------------------------------------ Final comments: ACK3D has evolved over the past few weeks into a reasonable 3D graphics engine and I am fairly pleased with the results thus far. There are, however some annoying nuances that still plague the engine. These can be summarized as follows, and in the words of most books "The rest is left as an exercise for the reader" (Man I hate those words!). a. Accuracy at certain angles is still an issue, every so often a wall sliver appears where it shouldn't, at least at the wrong height anyway. b. Objects are getting clipped off the screen when thier centerpoint is reached. They should be partially visible even if the center is not. c. Collision detection is far from perfect. A better method needs to be devised to handle coming up to walls and objects at any angle. d. Secret doors are mariginally working. They should be used with care since the side walls of the moving door are invisible until the secret door comes to a rest. e. Object movement is restricted to always turning right when bumping into an obstacle. This needs to have more smarts built in to allow moving objects to do things like chase the player, or run away, or follow some predetermined path, etc. f. Other types of doors, besides secret and sliding doors needs to be implemented. Future versions of the engine will handle a variety of doors to deal with different uses of the engine. g. The goal actions need to be enhanced beyond displaying a screen that says something on the order of YOU WON! I mean really.... I hope this discussion, and the 3D engine itself, prove to be a good starting point for your own creations. Many possibilities exist for this type of environment ranging from underground dungeons, to space stations, to art galleries. All thats needed is the right combination of graphics, sound, and storyline. Sincerely, Lary Myers 5 Jacob Street Ballston Lake, NY 12019 CIS Account: 76004,1574